Selection sort
In [11]:
# Python program for implementation of Selection
# Sort
import sys
A = [64, 25, 12, 22, 11]
# Traverse through all array elements
for i in range(len(A)):
# Find the minimum element in remaining
# unsorted array
min_idx = i
for j in range(i+1, len(A)):
if A[min_idx] > A[j]:
min_idx = j
# Swap the found minimum element with
# the first element
A[i], A[min_idx] = A[min_idx], A[i]
# Driver code to test above
print ("Sorted array")
for i in range(len(A)):
print("%d" %A[i]),
Bubble sort
In [12]:
# Python program for implementation of Bubble Sort
def bubbleSort(arr):
n = len(arr)
# Traverse through all array elements
for i in range(n):
# Last i elements are already in place
for j in range(0, n-i-1):
# traverse the array from 0 to n-i-1
# Swap if the element found is greater
# than the next element
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
# Driver code to test above
arr = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(arr)
print ("Sorted array is:")
for i in range(len(arr)):
print ("%d" %arr[i]),
In [14]:
# Python program for implementation of Insertion Sort
# Function to do insertion sort
def insertionSort(arr):
# Traverse through 1 to len(arr)
for i in range(1, len(arr)):
key = arr[i]
# Move elements of arr[0..i-1], that are
# greater than key, to one position ahead
# of their current position
j = i-1
while j >=0 and key < arr[j] :
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
# Driver code to test above
arr = [12, 11, 13, 5, 6]
insertionSort(arr)
for i in range(len(arr)):
print ("%d" %arr[i])
In [15]:
# Python program for implementation of MergeSort
def mergeSort(arr):
if len(arr) >1:
mid = len(arr)//2 #Finding the mid of the array
L = arr[:mid] # Dividing the array elements
R = arr[mid:] # into 2 halves
mergeSort(L) # Sorting the first half
mergeSort(R) # Sorting the second half
i = j = k = 0
# Copy data to temp arrays L[] and R[]
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i+=1
else:
arr[k] = R[j]
j+=1
k+=1
# Checking if any element was left
while i < len(L):
arr[k] = L[i]
i+=1
k+=1
while j < len(R):
arr[k] = R[j]
j+=1
k+=1
# Code to print the list
def printList(arr):
for i in range(len(arr)):
print(arr[i],end=" ")
print()
# driver code to test the above code
if __name__ == '__main__':
arr = [12, 11, 13, 5, 6, 7]
print ("Given array is", end="\n")
printList(arr)
mergeSort(arr)
print("Sorted array is: ", end="\n")
printList(arr)
Dutch National Flag
In [27]:
import random
colours_in_order = 'Red White Blue'.split()
def dutch_flag_sort(items):
lo, mid, hi = 0, 0, len(items)-1
while mid <= hi:
colour = items[mid]
if colour == 'Red':
items[lo], items[mid] = items[mid], items[lo]
lo += 1
mid += 1
elif colour == 'White':
mid += 1
else:
items[mid], items[hi] = items[hi], items[mid]
hi -= 1
print(items)
def dutch_flag_check(items, order=colours_in_order):
'Return True if each item of items is in the given order'
order_of_items = [order.index(item) for item in items]
return all(x <= y for x, y in zip(order_of_items, order_of_items[1:]))
def random_balls(mx=5):
'Select from 1 to mx balls of each colour, randomly'
balls = sum(([[colour] * random.randint(1, mx)
for colour in colours_in_order]), [])
random.shuffle(balls)
return balls
def main():
# Ensure we start unsorted
while 1:
balls = random_balls()
if not dutch_flag_check(balls):
break
print("Original Ball order:", balls)
dutch_flag_sort(balls)
print("Sorted Ball Order:", balls)
assert dutch_flag_check(balls), 'Whoops. Not sorted!'
if __name__ == '__main__':
main()
Jeremy's implementation
In [4]:
import random
colours_in_order = 'Red White Blue'.split()
def dutch_flag_sort(items):
r,w,b = 0,0,len(items)
while w<b:
if (items[w] == 'Red'):
items[r], items[w] = items[w], items[r]
r , w = r+1, w+1
elif (items[w] == 'White'):
w = w+1
else:
#item[w] == 'Blue'
items[w], items[b-1] = items[b-1], items[w]
b = b-1
def dutch_flag_check(items, order=colours_in_order):
'Return True if each item of items is in the given order'
order_of_items = [order.index(item) for item in items]
return all(x <= y for x, y in zip(order_of_items, order_of_items[1:]))
def random_balls(mx=5):
'Select from 1 to mx balls of each colour, randomly'
balls = sum(([[colour] * random.randint(1, mx)
for colour in colours_in_order]), [])
random.shuffle(balls)
return balls
def main():
# Ensure we start unsorted
while 1:
balls = random_balls()
if not dutch_flag_check(balls):
break
print("Original Ball order:", balls)
dutch_flag_sort(balls)
print("Sorted Ball Order:", balls)
assert dutch_flag_check(balls), 'Whoops. Not sorted!'
if __name__ == '__main__':
main()
Counting Sort
In [35]:
colours_in_order = 'Red White Blue'.split()
def counting_sort(items):
r,w,b = 0,0,0
for i in range(len(items)):
colour = items[i]
if(colour == 'Red'):
r= r+1
elif(colour == 'White'):
w= w+1
else:
b= b+1
for i in range(0, r):
items[i] = 'Red'
for i in range(r, r+w):
items[i] = 'White'
for i in range(r+w,r+w+b):
items[i] = 'Blue'
def counting_sort_check(items, order=colours_in_order):
'Return True if each item of items is in the given order'
order_of_items = [order.index(item) for item in items]
return all(x <= y for x, y in zip(order_of_items, order_of_items[1:]))
def random_balls(mx=5):
'Select from 1 to mx balls of each colour, randomly'
balls = sum(([[colour] * random.randint(1, mx)
for colour in colours_in_order]), [])
random.shuffle(balls)
return balls
def main():
# Ensure we start unsorted
while 1:
balls = random_balls()
if not counting_sort_check(balls):
break
print("Original Ball order:", balls)
counting_sort(balls)
print("Sorted Ball Order:", balls)
assert counting_sort_check(balls), 'Whoops. Not sorted!'
if __name__ == '__main__':
main()
Quick Sort
In [42]:
def quicksort(items):
less = []
more = []
pivotlist = []
if(len(items)<=1):
return items
else:
pivot = items[0]
for i in items:
if (i<pivot):
less.append(i)
elif (i>pivot):
more.append(i)
else:
pivotlist.append(i)
less = quicksort(less)
more = quicksort(more)
return less + pivotlist + more
a = [4, 65, 2, -31, 0, 99, 83, 782, 1]
a = quicksort(a)
print(a)
Jeremy's version
In [49]:
import statistics
def quicksort(myList, start, end):
if start < end:
# partition the list
pivot = partition(myList, start, end)
# sort both halves
quicksort(myList, start, pivot-1)
quicksort(myList, pivot+1, end)
return myList
def partition(myList, start, end):
pivot = 0
left = start+1
right = end
done = False
while not done:
while left <= right and myList[left] <= pivot:
left = left + 1
while myList[right] >= pivot and right >=left:
right = right -1
if right < left:
done= True
else:
# swap places
temp=myList[left]
myList[left]=myList[right]
myList[right]=temp
# swap start with myList[right]
temp=myList[start]
myList[start]=myList[right]
myList[right]=temp
return right
a = [-6, 65, 2, -31, 0, -99, 83, 782, 1]
a = quicksort(a, 0, len(a)-1)
print(a)
Shell Sort
In [47]:
def shell(seq):
increment = len(seq) // 2
while increment:
for i, el in enumerate(seq):
while i >= increment and seq[i - increment] > el:
seq[i] = seq[i - increment]
i -= increment
seq[i] = el
increment = 1 if increment == 2 else int(increment * 5.0 / 11)
data = [22, 7, 2, -5, 8, 4]
shell(data)
print(data)
In [50]:
def next_increment(i):
return (i-1)//2
def first_increment(n):
i =1
while i<n:
i=2*i+1
return next_increment(i)
In [51]:
def shell(A):
i = first_increment(len(A))
while i >0:
for j in range(0,len(A)-1):
t,k = A[j], j
while k >=i and t<A[k-i]:
A[k], k = A[k-i], k-i
A[k] = t
i= next_increment(i)
data = [22, 7, 2, -5, 8, 4]
shell(data)
print(data)
Exercises
In [43]:
def partition(A):
u, p = 0,len(A)-1
while(u!=p):
if(A[u]<0):
u = u+1
else:
A[u], A[p] = A[p], A[u]
p = p-1
return A
data = [-22, -7, -2, -5, 8, 4]
partition(data)
print(data)
In [58]:
def partition(a,p):
left = 1
right= len(a)-1
pivot = p
while(True):
while(a[left]< a[pivot]):
left = left +1
while (a[right]>a[pivot]):
right = right -1
if(left>=right):
a[right], a[0] = a[0], a[right]
return right
a[left], a[right] = a[right], a[left]
data = [-22, 7, -22, -52, 8, 4]
print(partition(data,0))
print(data)
In [65]:
def quickselect(a,k):
pivot = 0
i = partition(a,pivot)
left =i-1
right =i+1
if(k<left):
quickselect(a[:i],k)
elif(k<right):
return a[k]
else:
quickselect(a[i:],k)
data = [-22, 7, -2, -52, 8, 4]
print(quickselect(data,3))
In [ ]: